package com.hy.dp;

public class DifferentPaths2 {


    /**
     *
     * 63. 不同路径 II
     * 力扣题目链接
     *
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     *
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     *
     * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     *
     * 网格中的障碍物和空位置分别用 1 和 0 来表示。
     * 示例：
     * 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
     * 输出：2 解释：
     * 3x3 网格的正中间有一个障碍物。
     * 从左上角到右下角一共有 2 条不同的路径：
     * 向右 -> 向右 -> 向下 -> 向下
     * 向下 -> 向下 -> 向右 -> 向右
     *
     * dp 五部曲
     * 1.确定下标含义
     * 2.推导公式 dp[i][j] = dp[i-1][j] + dp[i][j-1]
     * 3.初始化 dp[0][i] = 1 dp[i][0] = 1
     * 4.循环遍历
     * 5.结果
     * @param grid
     * @return
     */
    public int differentPath2(int [][] grid){
        int m = grid.length;
        int n = grid[0].length;

        int [][] dp = new  int[m][n];
        // 初始化
        for (int i = 0; i < m; i++) {
            //一旦遇到障碍，后续都到不了
            if (grid[0][i] == 1){
                break;
            }
            dp[0][i] = 1;
        }
        for (int i = 0; i < n; i++) {
            //一旦遇到障碍，后续都到不了
            if (grid[i][0] == 1){
                break;
            }
            dp[i][0] = 1;
        }
        // 循环遍历
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //  一旦遇到障碍，后续都到不了
                if (grid[i][j] == 1){
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j - 1];
            }
        }
        return dp[m-1][n-1];
    }


    public static void main(String[] args) {
        DifferentPaths2 differentPaths2 = new DifferentPaths2();
        int [][]grid = {{0,0,0},{0,1,0},{0,0,0}};
        System.out.println("res : "+differentPaths2.differentPath2(grid));
    }

}
